#pragma once

#include <utility>
#include <vector>

class Solution
{
public:
    void nextPermutation(std::vector<int>& nums)
    {
        switch (nums.size()) {
            case 2: std::swap(nums.front(), nums.back());
            case 1: break;
            default: {
                int l = nums.size() - 2;
                int r = nums.size() - 1;
                for (; l >= 0; --r, --l) {
                    if (nums.at(l) < nums.at(r))
                        break;
                }
                if (l >= 0) {
                    for (++r; r < (int)nums.size(); ++r) {
                        if (nums.at(l) >= nums.at(r))
                            break;
                    }
                    std::swap(nums.at(l), nums.at(r - 1));
                }
                for (++l, r = nums.size() - 1; l < r; ++l, --r)
                    std::swap(nums.at(l), nums.at(r));
            }
        }
    }

    std::vector<int> nextPermutationNoInplace(std::vector<int> nums)
    {
        nextPermutation(nums);
        return nums;
    }

    std::vector<int> nextPermutationWithReturn(std::vector<int>& nums)
    {
        nextPermutation(nums);
        return nums;
    }
};
